/**
 * 1003. 检查替换后的词是否有效
 * https://leetcode-cn.com/problems/check-if-word-is-valid-after-substitutions/
 */
public class Solutions_1003 {
    public static void main(String[] args) {
//        String str ="aabcbc";  // output: true
//        String str ="abcabcababcc";  // output: true
//        String str ="abccba";  // output: false
        String str ="cababc";  // output: false
//        String str ="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";  // output: false

        boolean result = isValid(str);
        System.out.println(result);
    }

    /**
     * 解法一：栈
     * @param s
     * @return
     */
    public static boolean isValid(String s) {
        if (s.length() < 3) {
            return false;
        }
        char[] arr = s.toCharArray();
        char[] stack = new char[arr.length];
        int idx = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 'c') {
                // 字符 'c' 前一定要是 'ab'
                if (idx < 2 || stack[idx - 1] != 'b'|| stack[idx - 2] != 'a') {
                    return false;
                }
                idx -= 2;
                continue;
            }
            // 'a', 'b' 记录在栈中
            stack[idx++] = arr[i];
        }
        return idx == 0;
    }

    /**
     * 解法二：字符串替换
     * @param s
     * @return
     */
    public static boolean isValid2(String s) {
        while (s.indexOf("abc") > -1) {
            s = s.replace("abc", "");
        }
        return s.length() == 0;
    }
}
